package com.algorithm.liyc.combine;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 0040.组合总和II
 *
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用一次。
 * 说明：
 * 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。
 *
 *
 * 这道题目和39.组合总和如下区别：
 * 1. 本题candidates 中的每个数字在每个组合中只能使用一次。
 * 2. 本题数组candidates的元素是有重复的，而39.组合总和是无重复元素的数组candidates
 * 最后本题和39.组合总和要求一样，解集不能包含重复的组合。
 * @author Liyc
 * @date 2024/1/18 16:02
 **/

public class Solution5 {
    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    private boolean[] used;
    private int sum = 0;
    public List<List<Integer>> combinationSum1(int[] candidates, int target) {
        used = new boolean[candidates.length];
        // 加标志数组，用来辅助判断同层节点是否已经遍历
        Arrays.fill(used, false);
        // 为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        combinationSum2(candidates, target, 0);
        return result;
    }

    public void combinationSum2(int[] candidates, int target, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            // 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
            if (i > 0 && candidates[i - 1] == candidates[i] && !used[i - 1]) {
                continue;
            }
            sum += candidates[i];
            path.add(candidates[i]);
            used[i] = true;
            // 每个节点仅能选择一次，所以从下一位开始
            combinationSum2(candidates, target, i + 1);
            sum -= candidates[i];
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }


}
